/*
 * Region.h
 *
 *  Created on: 2012-9-20
 *      Author: yangentao@gmail.com
 */

#pragma once;
#include <algorithm>
#include "baseutil.h"
#include "Vector.h"

using namespace std;
namespace yet{
template<typename T>
class Region {
public:
	typedef Range<T> RangeType;
	Vector<RangeType> ranges;
	bool autoMerge;
public:
	Region(int capcity, bool autoMerge_) {
		ranges.init(Max(capcity, 4));
		autoMerge = autoMerge_;
	}
	Region(int capcity) {
		autoMerge = true;
		ranges.init(Max(capcity, 4));
	}
	Region(bool autoMerge_ = true) {
		autoMerge = autoMerge_;
	}
	virtual ~Region() {

	}

	void init(int capcity) {
		ranges.init(Max(4, capcity));
	}

	bool test() {
		if (ranges.empty()) {
			return true;
		}
		RangeType r = ranges.first();
		if (r.from >= r.to) {
			return false;
		}
		for (int i = 1; i < ranges.length(); ++i) {
			RangeType cr = ranges.get(i);
			if (r.from >= cr.from || r.to > cr.from) {
				return false;
			}
			if (cr.from >= cr.to) {
				return false;
			}
			if (autoMerge && cr.from == r.to && cr.value == r.value) {
				return false;
			}
			r = cr;
		}
		return true;
	}

public:
	inline int length() const {
		return ranges.length();
	}
	inline bool empty() const {
		return ranges.empty();
	}
	inline RangeType get(int index) const {
		return ranges[index];
	}
	inline void removeByIndex(int index) {
		ranges.remove(index);
	}

	void add(RangeType range) {
		if (empty()) {
			ranges.append(range);
			return;
		}
		RangeType* firstGE = lower_bound(ranges.beginW(), ranges.endW(), range);

		int delRight = 0; // mergeRight(range, firstGE);
		for (RangeType* next = firstGE; next < ranges.end(); ++next) {
			if (range.to >= next->to) { //eat
				++delRight;
				continue;
			} else if (range.to < next->from) { //no cross
				break;
			} else { //cross, merge
				if (mayMerge(&range, next)) {
					range.to = next->to;
					++delRight;
				} else {
					next->from = range.to;
				}
				break;
			}
		}

		RangeType* split = 0;
		int delLeft = 0;
		for (RangeType* pre = firstGE - 1; pre >= ranges.begin(); --pre) {
			if (range.from <= pre->from) { //full eat
				++delLeft;
				continue;
			} else if (range.from > pre->to) { //no cross
				break;
			} else { //cross
				if (mayMerge(pre, &range)) { //eat
					range.from = pre->from;
					++delLeft;
				} else {
					if (pre->to > range.to) { //split
						split = new RangeType(range.to, pre->to, pre->value);
					}
					pre->to = range.from;
				}
				break;
			}
		}

		if (split) {
			Vector<RangeType> vec(2);
			vec.append(range);
			vec.append(*split);
			ranges.replace(firstGE - ranges.begin() - delLeft, delRight + delLeft, vec);
		} else {
			ranges.replace(firstGE - ranges.begin() - delLeft, delRight + delLeft, &range, 1);
		}
	}

	inline void add(int from, int to, T value) {
		add(RangeType(from, to, value));
	}

	void remove(int from, int to) {
		remove(RangeType(from, to, T()));
	}

	void remove(RangeType range) {
		RangeType* begin = ranges.begin();
		RangeType* end = ranges.end();

		RangeType* firstPos = lower_bound(begin, end, range); //>=
		//remove left
		int delLeft = 0;
		RangeType* split = 0;
		for (RangeType* pre = firstPos - 1; pre >= begin; --pre) {
			if (pre->from >= range.from) {		//full eat
				++delLeft;
				continue;
			} else if (pre->to > range.from) {		//part remove
				if (pre->to > range.to) {
					split = new RangeType(range.to, pre->to, pre->value);
				}
				pre->to = range.from;
				break;
			} else {		//no cross
				break;
			}
		}

		//remove right
		int delRight = 0;
		for (RangeType* next = firstPos; next < end; ++next) {
			if (next->from > range.to) {		//no cross
				break;
			} else if (next->to <= range.to) {		//full eat
				++delRight;
			} else {
				next->from = range.to;
				break;
			}
		}
		ranges.replace(firstPos - begin - delLeft, delLeft + delRight, split, split ? 1 : 0);
	}

	Region<T> subRegion(int rangeFrom, int rangeTo) const {
		const RangeType* begin = ranges.begin();
		const RangeType* end = ranges.end();
		Region<T> rg(autoMerge);
		const RangeType* firstPos = lower_bound(begin, end, RangeType(rangeFrom, rangeFrom + 1));
		int len = 0;
		const RangeType* p = firstPos;
		for (; p < end; ++p) {
			if (p->from < rangeTo) {
				++len;
			} else {
				break;
			}
		}
		rg.ranges = ranges.sub(firstPos - begin, len);
		if (!rg.ranges.empty()) {
			RangeType* last = rg.ranges.endW() - 1;
			last->to = Min(last->to, rangeTo);
		}
		return rg;
	}
private:

	inline bool mayMerge(RangeType* left, RangeType* right) {
		return autoMerge && left->value == right->value;
	}

	int mergeRight(RangeType& range, RangeType* firstGE) {
		if (firstGE == 0 || firstGE == ranges.end()) {
			return 0;
		}
		int del = 0;

		for (RangeType* next = firstGE; next < ranges.end(); ++next) {
			if (range.to >= next->to) { //eat
				++del;
				continue;
			} else if (range.to < next->from) { //no cross
				break;
			} else { //cross, merge
				if (mayMerge(&range, next)) {
					range.to = next->to;
					++del;
				} else {
					next->from = range.to;
				}
				break;
			}
		}
		return del;

	}

};

typedef Region<int> IntRegion;

}
